package leetcode.od;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

/**
 * @author pppppp
 * @date 2022/3/28 12:00
 */
public class 信道分配 {
    @Test
    public void T_() {
        /*30 = 011110*/
        int[][] signals = {{60, 0, 0, 0, 0, 0}, {10, 5, 0, 1, 3, 2}, {0, 0, 0, 0, 0, 2}, {1, 1, 1, 1, 1, 2}, {29, 30, 30, 30, 31, 2}};
        int D = 30;
        int[] ans = {2, 4, 2, 3, 33};
        for (int i = 0; i < signals.length; i++) {
            // System.out.println(devideSignal(signals[i], D) == ans[i]);
            System.out.println(devideSignal_review(signals[i], D) == ans[i]);
        }
    }

    private int devideSignal_review(int[] signal, int d) {
        int res = 0;
        char[] s = new StringBuffer(Integer.toBinaryString(d)).reverse().toString().toCharArray();
        for (int i = s.length; i < signal.length; i++) {
            res += signal[i];
        }
        while (isVaild(signal, s)) {
            res++;
        }
        return res;
    }

    private boolean isVaild(int[] signal, char[] s) {

        ArrayList<Integer> list = new ArrayList<>();
        for (int i =0; i < s.length ; i++) {
            signal[i] -= Integer.valueOf(s[i] - '0');
            /*记录为 0 的位置*/
            if (signal[i] < 0) {
               list.add(i);
            }
        }
        /*把负数补齐 先向低位不为零的借位 再向高位借位*/
        if(list.size() > 0){
            for (Integer index : list) {
                int r = index+1,l = index-1,v = 1 << index;
                /*1.向低位(向左)借位*/
                while (l >= 0 && v > 0){
                    while (signal[l] > 0 && v > 0){
                        if(v > (1 << l)* signal[l]){
                            v -= (1 << l)* signal[l];
                            signal[l] = 0;
                        }else {
                            v -= 1 << l;
                            signal[l]--;
                        }
                    }
                    l--;
                }
                /*2.向高位(向左)借位*/
                while (r < s.length && v > 0 ){
                    if(signal[r] <= 0){
                        r++;
                    }else {
                        signal[r]--;
                        v -= 1 << r;
                    }
                }
                if(v > 0){
                    return false;
                }
                signal[index]++;
            }
        }
        return true;
    }

    /*二进制的减法处理*/
    private int devideSignal(int[] signal, int d) {
        int count = 0;
        /*将d变为二进制数*/
        int[] ds = new int[signal.length];
        for (int i = 0; i < signal.length; i++) {
            ds[i] = (d & (1 << i)) == 0 ? 0 : 1;
        }

        int endIndex = 0;
        for (int i = signal.length - 1; i >= 0; i--) {
            if (ds[i] == 1) {
                endIndex = i;
                break;
            }
            count += signal[i];
            signal[i] = 0;
        }
        while (isVaild(signal, ds, endIndex)) {
            count++;
        }
        return count;
    }

    private boolean isVaild(int[] signal, int[] ds, int endIndex) {
        for (int i = 0; i <= endIndex; i++) {
            signal[i] = signal[i] - ds[i];
            while (i < signal.length - 1 && signal[i] < 0) {
                signal[i + 1]--;
                signal[i] += 2;
            }
        }
        /*返回处理完的最高位*/
        /*凑高位*/
        if (signal[signal.length - 1] < 0) {
            int max = 1 << (signal.length - 1);
            /*将所有的数都加到1上*/
            for (int i = 1; i < signal.length - 1; i++) {
                signal[0] += signal[i] * (1 << i);
                signal[i] = 0;
            }

            if (signal[0] >= (1 << (signal.length - 1))) {
                signal[signal.length - 1] = signal[0] / max - 1;
                signal[0] = signal[0] % max;
                return true;
            }
        }
        return signal[signal.length - 1] >= 0;
    }
}
